using System;
using System.Linq;
using System.Collections.Generic;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0315. 计算右侧小于当前元素的个数")]
    public class No0315_CountSmaller : AbsBaseTestItem
    {
        public override void OnTest()
        {
            Assert.TestExe(CountSmaller,
                arg1: new int[] { 5, 2, 6, 1 },
                new List<int>() { 2, 1, 1, 0 });

            Assert.TestExe(CountSmaller,
                arg1: new int[] { 2, 0, 1 },
                new List<int>() { 2, 0, 0 });

            Assert.TestExe(CountSmaller,
                arg1: new int[] { 1, 0, 2 },
                new List<int>() { 1, 0, 0 });
        }

        public IList<int> CountSmaller(int[] nums)
        {
            int[] c;
            int[] a;
            void Init(int length)
            {
                c = new int[length];
                Array.Fill(c, 0);
            };
            int LowBit(int x)
            {
                return x & (-x);
            };
            void Update(int pos)
            {
                while (pos < c.Length)
                {
                    c[pos] += 1;
                    pos += LowBit(pos);
                }
            };
            int Query(int pos)
            {
                int ret = 0;
                while (pos > 0)
                {
                    ret += c[pos];
                    pos -= LowBit(pos);
                }
                return ret;
            };
            void Discretization(int[] nums)
            {
                a = (int[])nums.Clone();
                var hashSet = new HashSet<int>(a);
                a = hashSet.ToArray();
                Array.Sort(a);
            };
            int GetId(int x)
            {
                return Array.BinarySearch(a, x) + 1;
            };

            var resultList = new List<int>();
            Discretization(nums);
            Init(nums.Length + 5);
            for (int i = nums.Length - 1; i >= 0; --i)
            {
                var id = GetId(nums[i]);
                resultList.Add(Query(id - 1));
                Update(id);
            }
            resultList.Reverse();
            return resultList;
        }
    }
}
